package com.zhang.二叉树;

import com.zhang.printer.BinaryTreeInfo;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 张吉鑫
 * @Description 二叉树
 * @date 2021/3/13 19:01
 */
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;

    /**
     * @return 返回元素数量
     */
    public int size(){
        return size;
    }

    /**
     * 查看二叉搜索树是否为空
     * @return true为空 false为非空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        root = null;
        size = 0;
    }


    /**
     * 通过队列层序遍历判断是否为完全二叉树
     * @return true为完全二叉树 false为 不是完全二叉树
     */
    public boolean isComplete(){
        if (root == null){
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean b = false;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (b && !node.isLeaf()){
                //如果变量开关为true && 当前节点的左节点不为空 说明不是完全二叉树
                return false;
            }
            if (node.left != null){
                queue.offer(node.left);
            }else if (node.right != null){
                //如果当前的节点的左子节点为空 右节点不为空 说明不是完全二叉树
                return false;
            }
            //如果右节点为空 讲变量开关设置为true
            if (node.right != null){
                queue.offer(node.right);
            }else {
                b = true;
            }
        }
        return true;
    }

    /**
     * 通过队列层序遍历计算树的高度
     * @return 当前树的高度
     */
    public int height(){
        if (root == null){
            return 0;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        //count用来记录每层树的节点数量
        int count = 1;
        //sum用来记录当前节点树的高度
        int sum = 0;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            count--;
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }

            if (count == 0){
                // count == 0 时 代表当前层数的树节点遍历完毕
                // 树的高度自增一
                // 然后通过队列元素数量获取下一层树节点的数量
                sum++;
                count = queue.size();
            }
        }
        return sum;
    }

    /**
     * 递归计算高度
     * @return 返回数的高度
     */
    public int heightRecursion(){
        return heightRecursion(root);
    }

    private int heightRecursion(Node<E> node){
        if (node == null){
            return 0;
        }
        return 1 + Math.max(heightRecursion(node.left), heightRecursion(node.right));
    }

    /**
     * 获取元素来自定义展示方式
     * @param <E> 存储的元素类型
     */
    public static abstract class Visitor<E>{
        /**
         *如果stop为true 代表停止遍历
         */
        boolean stop;

        /**
         * 由用户实现遍历出来的元素操作方法
         * @param element 树节点的元素内容
         * @return 返回false继续遍历 返回true 停止遍历
         */
        public abstract boolean visitor(E element);
    }
    /**
     * 前序遍历(递归)
     */
    public void preorderTraversal(Visitor<E> visitor){
        preorderTraversal(root,visitor);
    }

    private void preorderTraversal(Node<E> node , Visitor<E> visitor){
        if (node == null || visitor.stop || visitor == null){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
    }

    /**
     * 通过双端队列模拟栈 进行前序遍历(迭代)
     */
    public void preorder(Visitor<E> visitor){
        if (root == null || visitor == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            visitor.visitor(node.element);
            if (node.right != null){
                deque.push(node.right);
            }
            if (node.left != null){
                deque.push(node.left);
            }
        }
    }
    /**
     * 中序遍历(递归)
     */
    public void inorderTraversal(Visitor<E> visitor){
        inorderTraversal(root,visitor);
    }

    private void inorderTraversal(Node<E> node , Visitor<E> visitor){
        if (node == null || visitor.stop || visitor == null){
            return;
        }
        inorderTraversal(node.left ,visitor);
        if (visitor.stop == true){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
        inorderTraversal(node.right ,visitor);
    }

    /**
     * 通过双端队列模拟栈 进行中序遍历(迭代)
     * @param visitor
     */
    public void inorder(Visitor<E> visitor){
        if (root == null || visitor == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            if (node.right != null){
                deque.push(node.right);
            }

            //如果当前节点时叶子节点就打印出来 如果不是叶子节点 就将当前节点的元素存入新节点 然后入栈
            if (node.isLeaf()){
                visitor.visitor(node.element);
            }else {
                deque.push(new Node<>(node.element, null));
            }

            if (node.left != null){
                deque.push(node.left);
            }
        }
    }

    /**
     * 后续遍历(递归)
     */
    public void postorderTraversal(Visitor<E> visitor){
        postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node , Visitor<E> visitor){
        if (node == null || visitor.stop || visitor == null){
            return;
        }
        postorderTraversal(node.left ,visitor);
        postorderTraversal(node.right ,visitor);
        if (visitor.stop == true){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
    }

    /**
     * 通过双端队列模拟栈 进行后续遍历(迭代)
     * @param visitor
     */
    public void postorder(Visitor<E> visitor){
        if (root == null || visitor == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            //如果当前节点为叶子节点就打印 否者将当前节点元素内容存入新节点 然后入栈
            if (node.isLeaf()){
                visitor.visitor(node.element);
            }else {
                deque.push(new Node<E>(node.element,null));
            }
            if (node.right != null){
                deque.push(node.right);
            }
            if (node.left != null){
                deque.push(node.left);
            }
        }
    }

    /**
     * 通过队列 进行层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null){
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<E> poll = queue.poll();
            if(visitor.visitor(poll.element)){
                return;
            };
            if (poll.left != null){
                queue.offer(poll.left);
            }
            if (poll.right != null){
                queue.offer(poll.right);
            }
        }
    }

    /**
     * @param node 当前节点
     * @return 获取当前节点的前驱节点
     */
    protected Node<E> predecessor(Node<E> node){

        if (node == null){
            return null;
        }

        if (node.left != null){
            Node<E> n = node.left;
            while (n.right != null){
                n = n.right;
            }
            return n;
        }
        while (node.parent != null && node == node.parent.left){
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 后继节点
     * @param node
     * @return
     */
    protected Node<E> successor(Node<E> node){
        if (node == null){
            return null;
        }
        if (node.right != null){
            Node<E> s = node.right;
            while (s.left != null){
                s = s.left;
            }
            return s;
        }
        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }

        return node.parent;
    }

    protected Node<E> createNode(E element,Node<E> parent){
        return new Node<>(element,parent);
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }

    protected static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element , Node<E> parent){
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断是否为叶子节点
         * @return
         */
        public boolean isLeaf(){
            return left == null && right == null;
        }

        /**
         * 判断是否有两个子节点
         * @return
         */
        public boolean hasTwoChildren(){
            return left != null && right != null;
        }

        /**
         * 判断是否是父节点的左子节点
         * @return
         */
        public boolean isLeftChild(){
            return parent != null && this == parent.left;
        }

        /**
         * 判断是否是父亲节点的右子节点
         * @return
         */
        public boolean isRightChild(){
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         * @return
         */
        public Node<E> sibling(){
            if (isLeftChild()){
                return parent.right;
            }
            if (isRightChild()){
                return parent.left;
            }

            return null;
        }
    }
}
